package Medium;

import java.util.Arrays;
import java.util.PriorityQueue;

public class LC2462 {
    class Worker implements Comparable<Worker> {
        int idx;
        int cost;

        public Worker(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Worker o) {
            return Integer.compare(this.cost, o.cost);
        }
    }

    /**
     * 我的解法，使用两个堆模拟选择过程
     */
    public long totalCost(int[] costs, int k, int candidates) {
        int n = costs.length;
        boolean[] isEmployed = new boolean[n];
        PriorityQueue<Worker> frontQueue = new PriorityQueue<>(), backQueue = new PriorityQueue<>();

        for (int i = 0; i < candidates; i++) {
            frontQueue.offer(new Worker(i, costs[i]));
            backQueue.offer(new Worker(n - 1 - i, costs[n - 1 - i]));
        }
        int frontPtr = candidates, backPtr = n - 1 - candidates;

        long totalCost = 0;
        for (int epoch = 0; epoch < k; epoch++) {
            while (!frontQueue.isEmpty() && isEmployed[frontQueue.peek().idx]) frontQueue.poll();
            while (!backQueue.isEmpty() && isEmployed[backQueue.peek().idx]) backQueue.poll();
            Worker frontCandidate = frontQueue.peek(), backCandidate = backQueue.peek();
            if (frontCandidate.cost <= backCandidate.cost) { // 输入保证两个对象一定不为空
                frontQueue.poll();
                isEmployed[frontCandidate.idx] = true;
                totalCost += frontCandidate.cost;
                while (frontPtr < n && isEmployed[frontPtr]) frontPtr++;
                if (frontPtr < n) {
                    frontQueue.offer(new Worker(frontPtr, costs[frontPtr]));
                    frontPtr++;
                }
                if (frontCandidate.idx > backPtr) { // 该候选者同时位于backQueue中
                    while (backPtr >= 0 && isEmployed[backPtr]) backPtr--;
                    if (backPtr >= 0) {
                        backQueue.offer(new Worker(backPtr, costs[backPtr]));
                        backPtr--;
                    }
                }
            }
            else {
                backQueue.poll();
                isEmployed[backCandidate.idx] = true;
                totalCost += backCandidate.cost;
                while (backPtr >= 0 && isEmployed[backPtr]) backPtr--;
                if (backPtr >= 0) {
                    backQueue.offer(new Worker(backPtr, costs[backPtr]));
                    backPtr--;
                }
                if (backCandidate.idx < frontPtr) {
                    while (frontPtr < n && isEmployed[frontPtr]) frontPtr++;
                    if (frontPtr < n) {
                        frontQueue.offer(new Worker(frontPtr, costs[frontPtr]));
                        frontPtr++;
                    }
                }
            }
        }
        return totalCost;
    }

    /**
     * 这个问题可以只用一个堆解决：将前candidates个元素和后candidates个元素放在一个堆里，堆中元素先按照cost排序，再按照idx排序
     */
    public static long totalCostSingleHeap(int[] costs, int k, int candidates) {
        int n = costs.length;
        long totalCost = 0;
        // 左右堆覆盖了整个数组，可以转化为直接找数组中k个最小元素。
        // 因为左堆中最小元素和右堆中最小元素之前更小的那个，就是整个数组中最小的元素。
        if (2 * candidates >= n) {
            Arrays.sort(costs);
            for (int i = 0; i < k; i++) totalCost += costs[i];
            return totalCost;
        }

        PriorityQueue<Integer> heap = new PriorityQueue<>((idx1, idx2) ->
                costs[idx1] != costs[idx2] ? costs[idx1] - costs[idx2] : idx1 - idx2);
        for (int i = 0; i < candidates; i++) {
            heap.offer(i);
            heap.offer(n - 1 - i);
        }

        // 双指针对撞
        int leftPtr = candidates, rightPtr = n - 1 - candidates;
        for (int epoch = 0; epoch < k; epoch++) {
            Integer idx = heap.poll();
            totalCost += costs[idx];
            if (leftPtr <= rightPtr) {
                if (idx < leftPtr) heap.offer(leftPtr++);
                else if (idx > rightPtr) heap.offer(rightPtr--);
            } // 如果leftPtr和rightPtr交叉，那么堆已经涵盖数组中剩余的所有元素，无需再插入
        }

        return totalCost;
    }

    public static void main(String[] args) {
        int[] costs = new int[]{17, 12, 10, 2, 7, 2, 11, 20, 8};
        System.out.println(totalCostSingleHeap(costs, 3, 4));
    }
}
